﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution39
{
    IList<IList<int>> res = new List<IList<int>>();
    public IList<IList<int>> CombinationSum(int[] candidates, int target)
    {

        IList<int> Combination=new List<int>();
        int sum = 0;
        int startIndex = 0;
        //DFS2(candidates, target, sum, Combination);
        DFS(candidates, target, sum, Combination,startIndex);
        return res;
    }

    private void DFS2(int[] candidates, int target, int sum, IList<int> combination)
    {
        if (sum > target)
        {

            return;
        }
        //递归终止的条件
        if (sum == target)
        {
            //加入数组
            //Console.WriteLine(sum);
            
            res.Add(combination);//这里应该加副本
            return;
        }
      

        for (int i = 0; i < candidates.Length; i++) {
            //可以选择加入或者不加入
            //不加入
            DFS2(candidates, target, sum, combination);//不加入，递归永远不停止，所有如果选择不加入，就要跳过
            //加入
            sum += candidates[i];
            IList<int> newcombination = new List<int>(combination);

            newcombination.Add(candidates[i]);
            DFS2(candidates, target, sum, newcombination);
            //combination.RemoveAt(combination.Count - 1);//回溯

        }
    }private void DFS3(int[] candidates, int target, int sum, IList<int> combination, int startIndex)
    {
        if (sum > target)
        {

            return;
        }
        //递归终止的条件
        if (sum == target)
        {
            //加入数组
            //Console.WriteLine(sum);
            IList<int> newcombination = new List<int>(combination);
            res.Add(newcombination);//这里应该加副本
            return;
        }

        //循环和两个递归选择一个就可以了

        //for (int i = startIndex; i < candidates.Length; i++)
        //{
        //    //可以选择加入或者不加入
        //    //不加入
        //    DFS(candidates, target, sum, combination, startIndex + 1);//不加入，递归永远不停止，所有如果选择不加入，就要跳过
        //    //加入
        //    sum += candidates[i];


        //    combination.Add(candidates[i]);
        //    DFS(candidates, target, sum, combination, startIndex);
        //    combination.RemoveAt(combination.Count - 1);//回溯

        //}

        //1,循环

        for (int i = startIndex; i < candidates.Length; i++)
        {
            

            //加入
            sum += candidates[i];


            combination.Add(candidates[i]);
            DFS3(candidates, target, sum, combination, i);
            combination.RemoveAt(combination.Count - 1);//回溯

            sum -= candidates[i];
        }


       




    }
    private void DFS(int[] candidates, int target, int sum, IList<int> combination, int startIndex)
    {
        if (sum > target)
        {

            return;
        }
        if (startIndex==candidates.Length)
        {
            return;

        }
        //递归终止的条件
        if (sum == target)
        {
            //加入数组
            //Console.WriteLine(sum);
            IList<int> newcombination = new List<int>(combination);
            res.Add(newcombination);//这里应该加副本
            return;
        }

      



        //2，递归
        //可以选择加入或者不加入
        //不加入

        DFS(candidates, target, sum, combination, startIndex + 1);//不加入，递归永远不停止，所有如果选择不加入，就要跳过，同时判断startIndex越界
                                                                  //加入


        sum += candidates[startIndex];
        combination.Add(candidates[startIndex]);
        DFS(candidates, target, sum, combination, startIndex);
        combination.RemoveAt(combination.Count - 1);//回溯




    }


}
class Program39
{


    static void Main39(string[] args)
    {

        Solution39 solution = new Solution39();
        int[] candidates = [2, 3, 6, 7];
        
        int target = 7;
        IList<IList<int>> res= solution.CombinationSum(candidates, target);
        for (int i = 0; i < res.Count; i++) { 
        
        for (int j = 0; j < res[i].Count; j++)
            {
                Console.Write(res[i][j]+"  ");
            }
            Console.WriteLine();
        }
    }
}
